package com.peng.tree.extend;


public class MySegmentTree {

    /*
    1、三个API：
    add（L,R,V）
    update（L,R,V）
    query（L,R）
    2、树结构、懒更新，懒住就会返回，懒不住要往下分发，分发之前先分发自身节点之前懒住的节点信息
    3、时间复杂度：O（logN）
     */


    private int N;
    private int[] originalArr;
    private int[] sumArr;
    private int[] lazyAddArr;
    private int[] lazyChangeArr;
    private boolean[] lazyUpdatedArr;

    public MySegmentTree(int[] originalArr) {
        N = originalArr.length + 1;
        this.originalArr = new int[N];
        this.sumArr = new int[N << 2];
        this.lazyAddArr = new int[N << 2];
        this.lazyChangeArr = new int[N << 2];
        this.lazyUpdatedArr = new boolean[N << 2];

        for (int i = 1; i < originalArr.length; i++) {
            this.originalArr[i] = originalArr[i - 1];
        }

    }

    /**
     * 把真实值先构建出来
     * <p>
     * L~R范围的累加和， pos为在数组中对应的位置
     *
     * @param L
     * @param R
     * @param pos
     */
    private void build(int L, int R, int pos) {
        if (L == R) {
            sumArr[pos] = originalArr[L];
            return;
        }

        int mid = L + ((R - L) >> 1);

        build(L, mid, pos << 1);

        build(mid + 1, R, pos << 1 | 1);

        setCurrentPosSum(pos);

    }


    private void add(int L, int R, int V, int currentL, int currentR, int currentPos) {


        //懒住！！
        if (L <= currentL && R >= currentR) {
            sumArr[currentPos] += (currentR - currentL + 1) * V;
            lazyAddArr[currentPos] += V;
            return;
        }

        //拦不住了，继续向下：
        //要先把现节点的懒更新分发到下面去
        int mid = currentL + ((currentR - currentL) >> 1);
        dispatchLazyData(currentPos, mid - currentL + 1, currentR - mid);

        //分发完毕，接下来开始分发任务


        /*
        task: 256-700
        example:

            1-1000
         1-500   501-1000

        1: 1~1000.no catch
        2: mid（1~1000） = 500，
        taskL<=mid? yes,dispatch task to left node
        taskR>mid? yes,dispatch task to right node


         */

        if (L <= mid) {
            add(L, R, V, currentL, mid, currentPos << 1);
        }

        if (R > mid) {
            add(L, R, V, mid + 1, currentR, currentPos << 1 | 1);
        }


        //最后，要更新当前节点的累加和信息
        setCurrentPosSum(currentPos);


    }


    private void update(int L, int R, int V, int currentL, int currentR, int currentPos) {


        //懒住！！
        if (L <= currentL && R >= currentR) {
            sumArr[currentPos] = (currentR - currentL + 1) * V;
            lazyAddArr[currentPos] = 0;
            lazyChangeArr[currentPos] = V;
            lazyUpdatedArr[currentPos] = true;
            return;
        }

        //拦不住了，继续向下：
        //要先把现节点的懒更新分发到下面去
        int mid = currentL + ((currentR - currentL) >> 1);
        dispatchLazyData(currentPos, mid - currentL + 1, currentR - mid);

        //分发完毕，接下来开始分发任务


        /*
        task: 256-700
        example:

            1-1000
         1-500   501-1000

        1: 1~1000.no catch
        2: mid（1~1000） = 500，
        taskL<=mid? yes,dispatch task to left node
        taskR>mid? yes,dispatch task to right node


         */

        if (L <= mid) {
            update(L, R, V, currentL, mid, currentPos << 1);
        }

        if (R > mid) {
            update(L, R, V, mid + 1, currentR, currentPos << 1 | 1);
        }


        //最后，要更新当前节点的累加和信息
        setCurrentPosSum(currentPos);


    }


    private int query(int L, int R, int currentL, int currentR, int currentPos) {


        //懒住！！
        if (L <= currentL && R >= currentR) {
            return sumArr[currentPos];
        }

        //拦不住了，继续向下：
        //要先把现节点的懒更新分发到下面去
        int mid = currentL + ((currentR - currentL) >> 1);
        dispatchLazyData(currentPos, mid - currentL + 1, currentR - mid);

        //分发完毕，接下来开始分发任务

        int result = 0;
        if (L <= mid) {
            result += query(L, R, currentL, mid, currentPos << 1);
        }

        if (R > mid) {
            result += query(L, R, mid + 1, currentR, currentPos << 1 | 1);
        }

        return result;

    }

    /**
     * 分发懒更新到子节点
     *
     * @param currentPos 当前的位置
     * @param leftCount  左节点的个数
     * @param rightCount 右节点的个数
     */
    private void dispatchLazyData(int currentPos, int leftCount, int rightCount) {

        if (lazyUpdatedArr[currentPos]) {
            sumArr[currentPos << 1] = leftCount * lazyChangeArr[currentPos];
            sumArr[currentPos << 1 | 1] = rightCount * lazyChangeArr[currentPos];
            lazyAddArr[currentPos << 1] = 0;
            lazyAddArr[currentPos << 1 | 1] = 0;
            lazyChangeArr[currentPos << 1] = lazyChangeArr[currentPos];
            lazyChangeArr[currentPos << 1 | 1] = lazyChangeArr[currentPos];
            lazyUpdatedArr[currentPos << 1] = true;
            lazyUpdatedArr[currentPos << 1 | 1] = true;
            lazyUpdatedArr[currentPos] = false;
        }
        if (lazyAddArr[currentPos] != 0) {
            sumArr[currentPos << 1] += leftCount * lazyAddArr[currentPos];
            sumArr[currentPos << 1 | 1] += rightCount * lazyAddArr[currentPos];
            lazyAddArr[currentPos << 1] += lazyAddArr[currentPos];
            lazyAddArr[currentPos << 1 | 1] += lazyAddArr[currentPos];
            //分发完毕，清空当前节点的懒信息
            lazyAddArr[currentPos] = 0;
        }
    }


    private void setCurrentPosSum(int pos) {
        sumArr[pos] = sumArr[pos << 1] + sumArr[pos << 1 | 1];
    }


    public static void main(String[] args) {

        int[] origin = {2, 1, 1, 2, 3, 4, 5};
        MySegmentTree seg = new MySegmentTree(origin);
        int S = 1; // 整个区间的开始位置，规定从1开始，不从0开始 -> 固定
        int N = origin.length; // 整个区间的结束位置，规定能到N，不是N-1 -> 固定
        int root = 1; // 整棵树的头节点位置，规定是1，不是0 -> 固定
        int L = 2; // 操作区间的开始位置 -> 可变
        int R = 5; // 操作区间的结束位置 -> 可变
        int C = 4; // 要加的数字或者要更新的数字 -> 可变

        seg.build(S, N, 1);

        seg.add(L, R, C, S, N, root);

        int query = seg.query(L, R, S, N, root);
        System.out.println(query);

        seg.update(L,R,C,S,N,root);
        query = seg.query(L, R, S, N, root);
        System.out.println(query);
        System.out.println("对数器测试开始...");
        System.out.println("测试结果 : " + (test() ? "通过" : "未通过"));

    }
    public static int[] genarateRandomArray(int len, int max) {
        int size = (int) (Math.random() * len) + 1;
        int[] origin = new int[size];
        for (int i = 0; i < size; i++) {
            origin[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
        }
        return origin;
    }
    public static boolean test() {
        int len = 100;
        int max = 1000;
        int testTimes = 5000;
        int addOrUpdateTimes = 1000;
        int queryTimes = 500;
        for (int i = 0; i < testTimes; i++) {
            int[] origin = genarateRandomArray(len, max);
            MySegmentTree seg = new MySegmentTree(origin);
            int S = 1;
            int N = origin.length;
            int root = 1;
            seg.build(S, N, root);
            Right rig = new Right(origin);
            for (int j = 0; j < addOrUpdateTimes; j++) {
                int num1 = (int) (Math.random() * N) + 1;
                int num2 = (int) (Math.random() * N) + 1;
                int L = Math.min(num1, num2);
                int R = Math.max(num1, num2);
                int C = (int) (Math.random() * max) - (int) (Math.random() * max);
                if (Math.random() < 0.5) {
                    seg.add(L, R, C, S, N, root);
                    rig.add(L, R, C);
                } else {
                    seg.update(L, R, C, S, N, root);
                    rig.update(L, R, C);
                }
            }
            for (int k = 0; k < queryTimes; k++) {
                int num1 = (int) (Math.random() * N) + 1;
                int num2 = (int) (Math.random() * N) + 1;
                int L = Math.min(num1, num2);
                int R = Math.max(num1, num2);
                long ans1 = seg.query(L, R, S, N, root);
                long ans2 = rig.query(L, R);
                if (ans1 != ans2) {
                    return false;
                }
            }
        }
        return true;
    }


    public static class Right {
        public int[] arr;

        public Right(int[] origin) {
            arr = new int[origin.length + 1];
            for (int i = 0; i < origin.length; i++) {
                arr[i + 1] = origin[i];
            }
        }

        public void update(int L, int R, int C) {
            for (int i = L; i <= R; i++) {
                arr[i] = C;
            }
        }

        public void add(int L, int R, int C) {
            for (int i = L; i <= R; i++) {
                arr[i] += C;
            }
        }

        public long query(int L, int R) {
            long ans = 0;
            for (int i = L; i <= R; i++) {
                ans += arr[i];
            }
            return ans;
        }

    }


}
